package lianxi;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2023-03-11
 * Time: 21:37
 */

/**
 * CC19 分割回文串-ii
 * 描述
 * 给出一个字符串s，分割s使得分割出的每一个子串都是回文串
 * 计算将字符串s分割成回文分割结果的最小切割数
 * 例如:给定字符串s="aab",
 * 返回1，因为回文分割结果["aa","b"]是切割一次生成的。
 * 示例1
 * 输入：
 * "aab"
 * 复制
 * 返回值：
 * 1
 */
public class Main3 {
    public static void main(String[] args) {
        int aab = minCut("ab");
        System.out.println(aab);
    }

    public  static boolean isPal(String s, int start, int end){
        while(start < end){
            if( s.charAt(start) != s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public  static int minCut(String s){
        if(s.length() == 0) return 0;
        if(isPal(s,0,s.length()-1)) return 0;
        int []mincut = new int[s.length()+1];
        //初始化
        for(int i=0;i<=s.length();i++){
            mincut[i] = i-1;
        }

        for(int i=1; i<=s.length();i++){
            if(isPal(s, 0,i-1)){
                mincut[i] =0;
                continue;
            }
            for(int j=0; j<i; j++){
                if(isPal(s,j,i-1)){
                    mincut[i]=Math.min(mincut[j]+1, mincut[i]);
                }
            }
        }
        return mincut[s.length()];

    }
}
